package com.explorati.LeetCode451;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 @ Author : Weijian_Wang
 * @ Date : Created in 23:08 2021/12/7 16:47
 * @ Description ：
 */
public class Solution {

    /**
     * 根据字符出现频率排序
     *
     * 输入:
     * "tree"
     *
     * 输出:
     * "eert"
     *
     * 解释:
     * 'e'出现两次，'r'和't'都只出现一次。
     * 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案
     *
     * @param s
     * @return
     */
    public String frequencySort(String s) {

        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i ++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        //最大堆 优先队列
        PriorityQueue<String[]> pq = new PriorityQueue<String[]>(new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return Integer.parseInt(o2[1]) - Integer.parseInt(o1[1]);
            }
        });

        for(Map.Entry entry : map.entrySet()) {
            pq.offer(new String[]{String.valueOf(entry.getKey()), String.valueOf(entry.getValue())});
        }

        StringBuilder result = new StringBuilder("");
        while(pq.size() > 0) {
            String[] currentStr = pq.poll();
            int currentStrfreq = Integer.parseInt(currentStr[1]);
            for(int i = 0; i < currentStrfreq; i ++) {
                result.append(currentStr[0]);
            }
        }

        return result.toString();
    }

}
